package com.yyt.bloonfilter.utils;

import java.util.BitSet;

/**
 * 布隆过滤器:：一个名叫 Bloom 的人提出了一种来检索元素是否在给定大集合中的数据结构，
 * 这种数据结构是高效且性能很好的，但缺点是具有一定的错误识别率和删除难度。
 * 并且，理论情况下，添加到集合中的元素越多，误报的可能性就越大。
 * <p>
 * 插入布隆过滤器：
 * 1、使用布隆过滤器中的哈希函数对元素值进行计算，得到哈希值（有几个哈希函数得到几个哈希值）。
 * 2、根据得到的哈希值，在位数组中把对应下标的值置为 1。
 * <p>
 * 判断值是否存在：
 * 1、对给定元素再次进行相同的哈希计算；
 * 2、得到值之后判断位数组中的每个元素是否都为 1，
 * 如果值都为 1，那么说明这个值在布隆过滤器中，
 * 如果存在一个值不为 1，说明该元素不在布隆过滤器中。
 * <p>
 * 使用场景
 * 判断给定数据是否存在：比如判断一个数字是否在于包含大量数字的数字集中（数字集很大，5亿以上！）、
 * 防止缓存穿透（判断请求的数据是否有效避免直接绕过缓存请求数据库）等等、
 * 邮箱的垃圾邮件过滤、黑名单功能等等。
 * 去重：比如爬给定网址的时候对已经爬取过的 URL 去重。
 *
 * @author yeyangtao
 * @date 2020/6/2 11:32
 */
public class MyBloomFilter {
    /**
     * 位数组大小 2^25
     */
    private static final int DEFAULT_SIZE = 2 << 24;

    private static final int[] SEEDS = new int[]{3, 13, 46, 71, 91, 134};

    private BitSet bits = new BitSet(DEFAULT_SIZE);

    private SimpleHash[] func = new SimpleHash[SEEDS.length];

    public MyBloomFilter() {
        for (int i = 0; i < SEEDS.length; i++) {
            func[i] = new SimpleHash(DEFAULT_SIZE, SEEDS[i]);
        }
    }

    public void add(Object value) {
        for (SimpleHash hash : func) {
            bits.set(hash.hash(value), true);
        }
    }

    public boolean contains(Object value) {
        boolean result = true;
        for (SimpleHash hash : func) {
            result = result && bits.get(hash.hash(value));
        }
        return result;
    }

    /**
     * 静态内部类。用于 hash 操作！
     */
    public static class SimpleHash {

        private int cap;
        private int seed;

        public SimpleHash(int cap, int seed) {
            this.cap = cap;
            this.seed = seed;
        }

        /**
         * 计算 hash 值
         */
        public int hash(Object value) {
            int h;
            return (value == null) ? 0 : Math.abs(seed * (cap - 1) & ((h = value.hashCode()) ^ (h >>> 16)));
        }
    }
}
